#include <string.h>
#include "gc.h"
#include "mem.h"
#include "rmath.h"
#include "redintobject.h"
#include "redmapobject.h"
#include "redboolobject.h"
#include "rednullobject.h"
#include "redarrayobject.h"
#include "redtupleobject.h"
#include "redstringobject.h"

#define RED_MAP_INIT_REDUCED		((RedObject *)1)

static RedObject *map_len(RedObject *self)
{
	return RedInt_FromInt(RedMap_Count(self));
}

static RedObject *map_repr(RedObject *self)
{
	int nmods;
	RedMap_ReadLock(self, nmods);

	if (RedMap_Count(self) == 0)
	{
		RedMap_Unlock(self);
		return RedString_FromCString("{}");
	}

	if (!RedObject_ReprEnter(self))
	{
		RedMap_Unlock(self);
		return RedString_FromCString("...");
	}

	int i = 0;
	RedObject *result = RedString_FromChar('{');
	RedMapNode *nodelist = RedMap_NodeList(self);

	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
	{
		RedObject *key = RedObject_Repr(node->key);

		if (!key)
		{
			Red_UNREF(result);
			RedObject_ReprLeave(self);
			RedMap_Unlock(self);
			return NULL;
		}

		RedObject *value = RedObject_Repr(node->value);

		if (!value)
		{
			Red_UNREF(key);
			Red_UNREF(result);
			RedObject_ReprLeave(self);
			RedMap_Unlock(self);
			return NULL;
		}

		if (!RedMap_CheckMods(self, nmods))
		{
			Red_UNREF(key);
			Red_UNREF(value);
			Red_UNREF(result);
			RedObject_ReprLeave(self);
			return NULL;
		}

		RedObject *item = RedString_AppendCString(key, ": ");
		RedObject *parts = RedString_Append(item, value);
		RedObject *newstring = RedString_Append(result, parts);

		Red_UNREF(key);
		Red_UNREF(item);
		Red_UNREF(parts);
		Red_UNREF(value);
		Red_UNREF(result);

		if (++i == RedMap_Count(self))
			result = RedString_AppendCString(newstring, "}");
		else
			result = RedString_AppendCString(newstring, ", ");

		Red_UNREF(newstring);
	}

	RedObject_ReprLeave(self);
	RedMap_Unlock(self);
	return result;
}


static char map_init(RedObject *self, RedObject *args)
{
	RedMutex_Init(RedMap_Mutex(self));

	/* initialize for reduced map */
	if (args == RED_MAP_INIT_REDUCED)
	{
		RedMap_NMods(self) = 0;
		RedMap_Count(self) = 0;
		RedMap_Pools(self) = RedMem_Alloc(sizeof(RedPoolNode) * RED_MAP_BUCKET_SIZE);

		if (!RedMap_Pools(self))
			return 0;

		RedMap_Intern(self) = 1;
		RedMap_PoolList(self)->lprev = RedMap_PoolList(self);
		RedMap_PoolList(self)->lnext = RedMap_PoolList(self);

		for (int i = 0; i < RED_MAP_BUCKET_SIZE; i++)
		{
			RedMap_Pools(self)[i].prev = &(RedMap_Pools(self)[i]);
			RedMap_Pools(self)[i].next = &(RedMap_Pools(self)[i]);
		}

		return 1;
	}

	if (!Red_INIT())
		return 0;

	RedMap_NMods(self) = 0;
	RedMap_Count(self) = 0;
	RedMap_Nodes(self) = RedMem_Alloc(sizeof(RedMapNode) * RED_MAP_BUCKET_SIZE);

	if (!RedMap_Nodes(self))
		return 0;
	
	RedMap_Intern(self) = 0;
	RedMap_NodeList(self)->lprev = RedMap_NodeList(self);
	RedMap_NodeList(self)->lnext = RedMap_NodeList(self);

	for (int i = 0; i < RED_MAP_BUCKET_SIZE; i++)
	{
		RedMap_Nodes(self)[i].prev = &(RedMap_Nodes(self)[i]);
		RedMap_Nodes(self)[i].next = &(RedMap_Nodes(self)[i]);
	}

	/* internal call */
	if (!args)
		return 1;

	if (!RedTuple_Exact(args))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'tuple' expected for 'args' argument");
		return 0;
	}

	/* only accepts `array` or `tuple` as its argument */
	int count = RedArray_Exact(args) ? RedArray_Length(args) :
				RedTuple_Exact(args) ? RedTuple_Length(args) : -1;

	if (count == -1)
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'tuple' or 'array' expected for 'args' argument");
		return 0;
	}

	for (int i = 0; i < count; i++)
	{
		/* `item` will never equals to NULL */
		RedObject *item = RedArray_Exact(args) ? RedArray_Items(args)[i] :
						  RedTuple_Exact(args) ? RedTuple_Items(args)[i] : NULL;

		/* only accepts format like '((k1, v1), (k2, v2), ....)' */
		if ((RedArray_Exact(item) ? RedArray_Length(item) :
			 RedTuple_Exact(item) ? RedTuple_Length(item) : -1) != 2)
		{
			RedException_ThrowFormat(&RedExc_TypeError, "'tuple' or 'array' expected for map items");
			return 0;
		}

		/* `k` and `v` will never equlas to NULL */
		RedObject *k = RedArray_Exact(item) ? RedArray_Items(item)[0] : RedTuple_Exact(item) ? RedTuple_Items(item)[0] : NULL;
		RedObject *v = RedArray_Exact(item) ? RedArray_Items(item)[1] : RedTuple_Exact(item) ? RedTuple_Items(item)[1] : NULL;

		/* put into bucket */
		if (!RedType_Map.tp_setitem(self, k, v))
			return 0;
	}

	return 1;
}

static void map_clear(RedObject *self)
{
	RedMapNode *node = RedMap_NodeList(self)->lnext;

	while (node != RedMap_NodeList(self))
	{
		RedMapNode *next = node->lnext;

		Red_UNREF(node->key);
		Red_UNREF(node->value);

		RedMem_Free(node);
		node = next;
	}

	RedMap_Count(self) = 0;
	RedMap_NodeList(self)->lnext = RedMap_NodeList(self);
}

static void map_release(RedObject *self)
{
	if (!RedMap_Intern(self))
	{
		map_clear(self);
		RedMem_Free(RedMap_Nodes(self));
		RedMutex_Free(RedMap_Mutex(self));
		Red_RELEASE();
	}
	else
	{
		RedPoolNode *node = RedMap_PoolList(self)->lnext;

		while (node != RedMap_PoolList(self))
		{
			RedPoolNode *next = node->lnext;

			Red_UNREF(node->value);
			RedMem_Free(node);
			node = next;
		}

		/* we have to clear the instance manually cause pool maps are not handled by parents */
		RedMem_Free(RedMap_Pools(self));
		RedMutex_Free(RedMap_Mutex(self));
		RedObject_GC_Free(self);
	}
}

static void map_traverse(RedObject *self, tp_visit_fn_t visit, void *args)
{
	RedMapNode *nodelist = RedMap_NodeList(self);
	
	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
	{
		Red_VISIT(node->key);
		Red_VISIT(node->value);
	}
}

static RedObject *map_eq(RedObject *self, RedObject *other)
{
	if (self == other)									Red_Return_True();
	if (!RedMap_Exact(other))							Red_Return_False();
	if (RedMap_Count(self) != RedMap_Count(other))		Red_Return_False();
	if (RedMap_StrKey(self) != RedMap_StrKey(other))	Red_Return_False();

	int nmods;
	RedMap_ReadLock(self, nmods);

	RedMapNode *nself = RedMap_NodeList(self)->lnext;
	RedMapNode *nother = RedMap_NodeList(other)->lnext;

	while (nself != RedMap_NodeList(self))
	{
		if (RedMap_StrKey(self))
		{
			if (!RedString_Equals(nself->key, nother->key))
			{
				RedMap_Unlock(self);
				Red_Return_False();
			}
		}
		else
		{
			RedObject *eq = RedObject_Eq(nself->key, nother->key);

			if (!eq)
			{
				RedMap_Unlock(self);
				return NULL;
			}

			if (!RedBool_IsTrue(eq))
			{
				Red_UNREF(eq);
				RedMap_Unlock(self);
				Red_Return_False();
			}

			if (!RedMap_CheckMods(self, nmods))
			{
				Red_UNREF(eq);
				return NULL;
			}

			Red_UNREF(eq);
		}

		RedObject *eq = RedObject_Eq(nself->value, nother->value);

		if (!eq)
		{
			RedMap_Unlock(self);
			return NULL;
		}

		if (!RedBool_IsTrue(eq))
		{
			Red_UNREF(eq);
			RedMap_Unlock(self);
			Red_Return_False();
		}

		if (!RedMap_CheckMods(self, nmods))
		{
			Red_UNREF(eq);
			return NULL;
		}

		Red_UNREF(eq);
		nself = nself->next;
		nother = nother->next;
	}

	RedMap_Unlock(self);
	Red_Return_True();
}

static RedObject *map_neq(RedObject *self, RedObject *other)
{
	RedObject *eq = map_eq(self, other);

	if (!eq)
		return NULL;

	if (!RedBool_IsTrue(eq))
	{
		Red_UNREF(eq);
		Red_Return_True();
	}
	else
	{
		Red_UNREF(eq);
		Red_Return_False();
	}
}

static RedObject *map_delitem(RedObject *self, RedObject *key)
{
	if (!RedMap_Del(self, key))
		return NULL;
	else
		Red_Return_Null();
}

static RedObject *map_setitem(RedObject *self, RedObject *key, RedObject *value)
{
	if (!RedMap_Put(self, key, value))
		return NULL;
	else
		Red_Return_Null();
}

static RedObject *map_keys(RedObject *self, RedObject *args)
{
	return RedTuple_Unpack(args, "") ? RedMap_Keys(self) : NULL;
}

static RedObject *map_items(RedObject *self, RedObject *args)
{
	return RedTuple_Unpack(args, "") ? RedMap_Items(self) : NULL;
}

static RedObject *map_values(RedObject *self, RedObject *args)
{
	return RedTuple_Unpack(args, "") ? RedMap_Values(self) : NULL;
}

static RedObject *map_pop(RedObject *self, RedObject *args)
{
	RedObject *key;
	RedObject *result;

	if (!RedTuple_Unpack(args, "?", &key))
		return NULL;

	if (!(result = RedMap_Get(self, key)))
		return NULL;

	Red_REF(result);
	RedMap_Del(self, key);
	return result;
}

static RedObject *map_clear_(RedObject *self, RedObject *args)
{
	if (!RedTuple_Unpack(args, ""))
		return NULL;

	RedMap_Clear(self);
	Red_Return_Null();
}

static RedObject *map_clone(RedObject *self, RedObject *args)
{
	return RedTuple_Unpack(args, "") ? RedMap_Clone(self) : NULL;
}

static RedObject *map_extend(RedObject *self, RedObject *args)
{
	RedObject *other;
	return RedTuple_Unpack(args, "m", &other) ? RedMap_Extend(self, other) : NULL;
}

typedef struct _mf_ctx_t
{
	int idx;
	RedObject *list;
	RedObject *callable;
} mf_ctx_t;

static char _map_foreach(RedObject *key, RedObject *value, void *context)
{
	mf_ctx_t *ctx = (mf_ctx_t *)context;
	RedObject *args = RedTuple_FromObjects(2, key, value);
	RedObject *result = RedObject_Invoke(ctx->callable, args);

	if (!result)
	{
		Red_UNREF(args);
		return 0;
	}

	Red_UNREF(args);
	RedTuple_Items(ctx->list)[ctx->idx++] = result;
	return 1;
}

static RedObject *map_foreach(RedObject *self, RedObject *args)
{
	RedObject *callable;

	if (!RedTuple_Unpack(args, "C", &callable))
		return NULL;

	mf_ctx_t context =
	{
		.idx = 0,
		.list = RedTuple_FromLength(RedMap_Count(self)),
		.callable = callable,
	};

	if (RedMap_Foreach(self, _map_foreach, &context))
		return context.list;

	for (int i = context.idx; i < RedMap_Count(self); i++)
		RedTuple_Items(context.list)[i] = NULL;

	Red_UNREF(context.list);
	return NULL;
}

static RedObject *map_contains(RedObject *self, RedObject *args)
{
	RedObject *key;

	if (!RedTuple_Unpack(args, "?", &key))
		return NULL;

	if (RedMap_HasKey(self, key))
		Red_Return_True();
	else
		Red_Return_False();
}

static RedMethodDesc map_methods[] =
{
	{ "keys"		, map_keys		},
	{ "items"		, map_items		},
	{ "values"		, map_values	},

	{ "pop"			, map_pop		},
	{ "clear"		, map_clear_	},
	{ "clone"		, map_clone		},
	{ "extend"		, map_extend	},
	{ "foreach"		, map_foreach	},
	{ "contains"	, map_contains	},
};

RedTypeObject RedType_Map =
{
	RedType_INIT("map", RedMapObject, RedType_Object)

	.tp_len			= map_len,
	.tp_str			= map_repr,
	.tp_repr		= map_repr,
	.tp_init		= map_init,
	.tp_clear		= map_clear,
	.tp_release		= map_release,
	.tp_traverse	= map_traverse,

	.tp_eq			= map_eq,
	.tp_neq			= map_neq,
	.tp_add			= RedMap_Concat,
	.tp_aug_add		= RedMap_Extend,

	.tp_getitem		= RedMap_Get,
	.tp_delitem		= map_delitem,
	.tp_setitem		= map_setitem,
	.tp_methods		= map_methods,
};

RedObject *RedMap_Create(void)
{
	RedObject *result = RedObject_Create(&RedType_Map, NULL);

	if (!result)
		return NULL;

	RedMap_StrKey(result) = 0;
	return result;
}

RedObject *RedMap_CreateStringKey(void)
{
	RedObject *result = RedObject_Create(&RedType_Map, NULL);

	if (!result)
		return NULL;

	RedMap_StrKey(result) = 1;
	return result;
}

char RedMap_Del(RedObject *self, RedObject *key)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "`map` expected for `self` argument");
		return 0;
	}

	if (RedMap_StrKey(self) && !RedString_Exact(key))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "Key type incompatible");
		return 0;
	}

	uint32_t hash = RedObject_Hash(key);

	if (hash == 0)
		return 0;

	int nmods;
	RedMap_WriteLock(self, nmods);

	int idx = hash % RED_MAP_BUCKET_SIZE;
	RedMapNode *list = &(RedMap_Nodes(self)[idx]);

	for (RedMapNode *node = list->next; node != list; node = node->next)
	{
		if (hash == node->hash)
		{
			if (RedMap_StrKey(self))
			{
				if (!RedString_Equals(key, node->key))
					continue;
			}
			else
			{
				RedObject *eq = RedObject_Eq(key, node->key);

				if (!eq)
				{
					RedMap_Unlock(self);
					return 0;
				}

				char found = RedBool_IsTrue(eq);

				if (!RedMap_CheckMods(self, nmods))
				{
					Red_UNREF(eq);
					return 0;
				}

				if (!found)
				{
					Red_UNREF(eq);
					continue;
				}

				Red_UNREF(eq);
			}

			Red_UNREF(node->key);
			Red_UNREF(node->value);

			node->prev->next = node->next;
			node->next->prev = node->prev;
			node->lprev->lnext = node->lnext;
			node->lnext->lprev = node->lprev;

			RedMem_Free(node);
			RedMap_Count(self)--;
			RedMap_Unlock(self);
			return 1;
		}
	}

	RedMap_Unlock(self);
	RedException_ThrowFormat(&RedExc_IndexError, "Key doesn't exists");
	return 0;
}

char RedMap_Put(RedObject *self, RedObject *key, RedObject *value)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "`map` expected for `self` argument");
		return 0;
	}

	if (RedMap_StrKey(self) && !RedString_Exact(key))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "Key type incompatible");
		return 0;
	}

	uint32_t hash = RedObject_Hash(key);

	if (hash == 0)
		return 0;

	int nmods;
	RedMap_WriteLock(self, nmods);

	int idx = hash % RED_MAP_BUCKET_SIZE;
	RedMapNode *list = &(RedMap_Nodes(self)[idx]);

	for (RedMapNode *node = list->next; node != list; node = node->next)
	{
		if (hash == node->hash)
		{
			if (RedMap_StrKey(self))
			{
				if (!RedString_Equals(key, node->key))
					continue;
			}
			else
			{
				RedObject *eq = RedObject_Eq(key, node->key);

				if (!eq)
				{
					RedMap_Unlock(self);
					return 0;
				}

				char found = RedBool_IsTrue(eq);

				if (!RedMap_CheckMods(self, nmods))
				{
					Red_UNREF(eq);
					return 0;
				}

				if (!found)
				{
					Red_UNREF(eq);
					continue;
				}

				Red_UNREF(eq);
			}

			Red_REF(value);
			Red_UNREF(node->value);

			node->value = value;
			RedMap_Unlock(self);

			if (RedObject_GC_IsTracked(self))
				RedObject_GC_Insert(value);

			return 1;
		}
	}

	RedMapNode *node = RedMem_Alloc(sizeof(RedMapNode));

	if (!node)
	{
		RedMap_Unlock(self);
		return 0;
	}

	node->key = key;
	node->hash = hash;
	node->value = value;

	Red_REF(node->key);
	Red_REF(node->value);

	node->next = list;
	node->prev = list->prev;
	list->prev->next = node;
	list->prev = node;

	node->lnext = RedMap_NodeList(self);
	node->lprev = RedMap_NodeList(self)->lprev;
	RedMap_NodeList(self)->lprev->lnext = node;
	RedMap_NodeList(self)->lprev = node;

	RedMap_Count(self)++;
	RedMap_Unlock(self);

	if (RedObject_GC_IsTracked(self))
	{
		RedObject_GC_Insert(key);
		RedObject_GC_Insert(value);
	}

	return 1;
}

RedObject *RedMap_Get(RedObject *self, RedObject *key)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "`map` expected for `self` argument");
		return NULL;
	}

	if (RedMap_StrKey(self) && !RedString_Exact(key))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "Key type incompatible");
		return NULL;
	}

	uint32_t hash = RedObject_Hash(key);

	if (hash == 0)
		return NULL;

	int nmods;
	RedMap_ReadLock(self, nmods);

	int idx = hash % RED_MAP_BUCKET_SIZE;
	RedMapNode *list = &(RedMap_Nodes(self)[idx]);

	for (RedMapNode *node = list->next; node != list; node = node->next)
	{
		if (hash == node->hash)
		{
			if (RedMap_StrKey(self))
			{
				if (RedString_Equals(key, node->key))
				{
					RedMap_Unlock(self);
					return node->value;
				}
			}
			else
			{
				RedObject *eq = RedObject_Eq(key, node->key);

				if (!eq)
				{
					RedMap_Unlock(self);
					return NULL;
				}

				if (RedBool_IsTrue(eq))
				{
					Red_UNREF(eq);
					RedMap_Unlock(self);
					return node->value;
				}

				if (!RedMap_CheckMods(self, nmods))
				{
					Red_UNREF(eq);
					return NULL;
				}

				Red_UNREF(eq);
			}
		}
	}

	RedMap_Unlock(self);
	RedException_ThrowFormat(&RedExc_IndexError, "Key doesn't exists");
	return NULL;
}

char RedMap_DelString(RedObject *self, RedObject *key)
{
	int nmods;
	RedMap_WriteLock(self, nmods);

	uint32_t hash = RedObject_Hash(key);
	RedMapNode *list = &(RedMap_Nodes(self)[hash % RED_MAP_BUCKET_SIZE]);

	for (RedMapNode *node = list->next; node != list; node = node->next)
	{
		if (hash == node->hash && RedString_Equals(key, node->key))
		{
			Red_UNREF(node->key);
			Red_UNREF(node->value);

			node->prev->next = node->next;
			node->next->prev = node->prev;
			node->lprev->lnext = node->lnext;
			node->lnext->lprev = node->lprev;

			RedMem_Free(node);
			RedMap_Count(self)--;
			RedMap_Unlock(self);
			return 1;
		}
	}

	RedMap_Unlock(self);
	return 0;
}

char RedMap_PutString(RedObject *self, RedObject *key, RedObject *value)
{
	int nmods;
	RedMap_WriteLock(self, nmods);

	uint32_t hash = RedObject_Hash(key);
	RedMapNode *list = &(RedMap_Nodes(self)[hash % RED_MAP_BUCKET_SIZE]);

	for (RedMapNode *node = list->next; node != list; node = node->next)
	{
		if (hash == node->hash && RedString_Equals(key, node->key))
		{
			Red_REF(value);
			Red_UNREF(node->value);

			node->value = value;
			RedMap_Unlock(self);

			if (RedObject_GC_IsTracked(self))
				RedObject_GC_Insert(value);

			return 1;
		}
	}

	RedMapNode *node = RedMem_Alloc(sizeof(RedMapNode));

	node->key = key;
	node->hash = hash;
	node->value = value;

	Red_REF(node->key);
	Red_REF(node->value);

	node->next = list;
	node->prev = list->prev;
	list->prev->next = node;
	list->prev = node;

	node->lnext = RedMap_NodeList(self);
	node->lprev = RedMap_NodeList(self)->lprev;
	RedMap_NodeList(self)->lprev->lnext = node;
	RedMap_NodeList(self)->lprev = node;

	RedMap_Count(self)++;
	RedMap_Unlock(self);

	if (RedObject_GC_IsTracked(self))
	{
		RedObject_GC_Insert(node->key);
		RedObject_GC_Insert(node->value);
	}

	return 1;
}

RedObject *RedMap_GetString(RedObject *self, RedObject *key)
{
	int nmods;
	RedMap_ReadLock(self, nmods);

	uint32_t hash = RedObject_Hash(key);
	RedMapNode *list = &(RedMap_Nodes(self)[hash % RED_MAP_BUCKET_SIZE]);

	for (RedMapNode *node = list->next; node != list; node = node->next)
	{
		if (hash == node->hash && RedString_Equals(key, node->key))
		{
			RedMap_Unlock(self);
			return node->value;
		}
	}

	RedMap_Unlock(self);
	return NULL;
}

RedObject *RedMap_Keys(RedObject *self)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'self' argument");
		return NULL;
	}

	int nmods;
	RedMap_ReadLock(self, nmods);

	int i = 0;
	RedObject *result = RedTuple_FromLength(RedMap_Count(self));
	RedMapNode *nodelist = RedMap_NodeList(self);

	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
	{
		Red_REF(node->key);
		RedTuple_Items(result)[i++] = node->key;
	}

	RedMap_Unlock(self);

	if (RedObject_GC_IsTracked(self))
		RedObject_GC_Insert(result);

	return result;
}

RedObject *RedMap_Items(RedObject *self)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'self' argument");
		return NULL;
	}

	int nmods;
	RedMap_ReadLock(self, nmods);

	int i = 0;
	RedObject *result = RedTuple_FromLength(RedMap_Count(self));
	RedMapNode *nodelist = RedMap_NodeList(self);

	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
	{
		RedObject *tuple = RedTuple_FromLength(2);

		if (RedObject_GC_IsTracked(self))
			RedObject_GC_Insert(tuple);

		Red_REF(node->key);
		Red_REF(node->value);
		RedTuple_Items(tuple)[0] = node->key;
		RedTuple_Items(tuple)[1] = node->value;
		RedTuple_Items(result)[i++] = tuple;
	}

	RedMap_Unlock(self);

	if (RedObject_GC_IsTracked(self))
		RedObject_GC_Insert(result);

	return result;
}

RedObject *RedMap_Values(RedObject *self)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'self' argument");
		return NULL;
	}

	int nmods;
	RedMap_ReadLock(self, nmods);

	int i = 0;
	RedObject *result = RedTuple_FromLength(RedMap_Count(self));
	RedMapNode *nodelist = RedMap_NodeList(self);

	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
	{
		Red_REF(node->value);
		RedTuple_Items(result)[i++] = node->value;
	}

	RedMap_Unlock(self);

	if (RedObject_GC_IsTracked(self))
		RedObject_GC_Insert(result);

	return result;
}

void RedMap_Clear(RedObject *self)
{
	int nmods;
	RedMap_WriteLock(self, nmods);

	map_clear(self);
	memset(RedMap_Nodes(self), 0, sizeof(RedMapNode) * RED_MAP_BUCKET_SIZE);
	RedMap_Unlock(self);
}

RedObject *RedMap_Clone(RedObject *self)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'self' argument");
		return NULL;
	}

	int nmods;
	RedObject *result = NULL;

	if (!RedMap_StrKey(self))
		result = RedMap_Create();
	else
		result = RedMap_CreateStringKey();

	if (!result)
		return NULL;

	RedMap_ReadLock(self, nmods);
	RedMapNode *nodelist = RedMap_NodeList(self);

	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
		if (!RedMap_StrKey(self))
			RedMap_Put(result, node->key, node->value);
		else
			RedMap_PutString(result, node->key, node->value);

	RedMap_Unlock(self);

	if (RedObject_GC_IsTracked(self))
		RedObject_GC_Insert(result);

	return result;
}

RedObject *RedMap_Concat(RedObject *self, RedObject *other)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'self' argument");
		return NULL;
	}

	if (!RedMap_Exact(other))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'other' argument");
		return NULL;
	}

	if (RedMap_StrKey(self) && !RedMap_StrKey(other))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "Key type incompatible");
		return NULL;
	}

	int nmods;
	RedMap_ReadLock(other, nmods);

	RedObject *result = RedMap_Clone(self);
	RedMapNode *nodelist = RedMap_NodeList(other);

	if (!result)
	{
		RedMap_Unlock(other);
		return NULL;
	}

	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
		if (!RedMap_StrKey(self))
			RedMap_Put(result, node->key, node->value);
		else
			RedMap_PutString(result, node->key, node->value);

	RedMap_Unlock(other);
	return result;
}

RedObject *RedMap_Extend(RedObject *self, RedObject *other)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'self' argument");
		return NULL;
	}

	if (!RedMap_Exact(other))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'other' argument");
		return NULL;
	}

	if (RedMap_StrKey(self) && !RedMap_StrKey(other))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "Key type incompatible");
		return NULL;
	}

	int nmods;
	RedMap_ReadLock(other, nmods);

	RedMapNode *nodelist = RedMap_NodeList(other);

	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
		if (!RedMap_StrKey(self))
			RedMap_Put(self, node->key, node->value);
		else
			RedMap_PutString(self, node->key, node->value);

	RedMap_Unlock(other);
	Red_Return_Null();
}

char RedMap_HasKey(RedObject *self, RedObject *key)
{
	if (RedMap_StrKey(self))
		return RedMap_GetString(self, key) ? 1 : 0;

	if (RedMap_Get(self, key))
		return 1;

	/* RedMap_Get may throw exceptions when key not found */
	RedException_Clear();
	return 0;
}

char RedMap_Foreach(RedObject *self, RedMapEnumerator callback, void *context)
{
	if (!RedMap_Exact(self))
	{
		RedException_ThrowFormat(&RedExc_TypeError, "'map' expected for 'self' argument");
		return 0;
	}

	int nmods;
	RedMap_ReadLock(self, nmods);

	RedMapNode *nodelist = RedMap_NodeList(self);

	for (RedMapNode *node = nodelist->lnext; node != nodelist; node = node->lnext)
	{
		if (!callback(node->key, node->value, context))
		{
			RedMap_Unlock(self);
			return 0;
		}

		if (!RedMap_CheckMods(self, nmods))
			return 0;
	}

	RedMap_Unlock(self);
	return 1;
}

/* internal functions */

RedObject *RedPool_Create(void)
{
	return RedObject_Create(&RedType_Map, RED_MAP_INIT_REDUCED);
}

char RedPool_DelInt(RedObject *self, int64_t key)
{
	int nmods;
	RedMap_WriteLock(self, nmods);

	uint32_t hash = rmath_hash_i64(key);
	RedPoolNode *list = &(RedMap_Pools(self)[hash % RED_MAP_BUCKET_SIZE]);

	for (RedPoolNode *node = list->next; node != list; node = node->next)
	{
		if (key == node->key_i64)
		{
			Red_UNREF(node->value);

			node->prev->next = node->next;
			node->next->prev = node->prev;
			node->lprev->lnext = node->lnext;
			node->lnext->lprev = node->lprev;

			RedMem_Free(node);
			RedMap_Count(self)--;
			RedMap_Unlock(self);
			return 1;
		}
	}

	return 0;
}

void RedPool_PutInt(RedObject *self, int64_t key, RedObject *value)
{
	int nmods;
	RedMap_WriteLock(self, nmods);

	uint32_t hash = rmath_hash_i64(key);
	RedPoolNode *node = RedMem_Alloc(sizeof(RedPoolNode));
	RedPoolNode *list = &(RedMap_Pools(self)[hash % RED_MAP_BUCKET_SIZE]);

	node->value = value;
	node->key_i64 = key;

	Red_REF(node->value);

	node->next = list;
	node->prev = list->prev;
	list->prev->next = node;
	list->prev = node;

	node->lnext = RedMap_PoolList(self);
	node->lprev = RedMap_PoolList(self)->lprev;
	RedMap_PoolList(self)->lprev->lnext = node;
	RedMap_PoolList(self)->lprev = node;
	RedMap_Count(self)++;
	RedMap_Unlock(self);
}

RedObject *RedPool_GetInt(RedObject *self, int64_t key)
{
	int nmods;
	RedMap_ReadLock(self, nmods);

	uint32_t hash = rmath_hash_i64(key);
	RedPoolNode *list = &(RedMap_Pools(self)[hash % RED_MAP_BUCKET_SIZE]);

	for (RedPoolNode *node = list->next; node != list; node = node->next)
	{
		if (key == node->key_i64)
		{
			RedObject *item = node->value;

			Red_REF(item);
			RedMap_Unlock(self);
			return item;
		}
	}

	RedMap_Unlock(self);
	return NULL;
}

void RedPool_PutString(RedObject *self, const char *s, int len, RedObject *value)
{
	int nmods;
	RedMap_WriteLock(self, nmods);

	uint32_t hash = rmath_hash_str(s, len);
	RedPoolNode *node = RedMem_Alloc(sizeof(RedPoolNode));
	RedPoolNode *list = &(RedMap_Pools(self)[hash % RED_MAP_BUCKET_SIZE]);

	node->value = value;
	node->key_strl = len;
	node->key_strhash = hash;

	memcpy(node->key_strp, s, len);
	Red_REF(node->value);

	node->next = list;
	node->prev = list->prev;
	list->prev->next = node;
	list->prev = node;

	node->lnext = RedMap_PoolList(self);
	node->lprev = RedMap_PoolList(self)->lprev;
	RedMap_PoolList(self)->lprev->lnext = node;
	RedMap_PoolList(self)->lprev = node;
	RedMap_Count(self)++;
	RedMap_Unlock(self);
}

RedObject *RedPool_GetString(RedObject *self, const char *s, int len)
{
	int nmods;
	RedMap_ReadLock(self, nmods);

	uint32_t hash = rmath_hash_str(s, len);
	RedPoolNode *list = &(RedMap_Pools(self)[hash % RED_MAP_BUCKET_SIZE]);

	for (RedPoolNode *node = list->next; node != list; node = node->next)
	{
		if (len == node->key_strl &&
			hash == node->key_strhash &&
			!memcmp(s, node->key_strp, len))
		{
			RedObject *item = node->value;

			Red_REF(item);
			RedMap_Unlock(self);
			return item;
		}
	}

	RedMap_Unlock(self);
	return NULL;
}
